Conventionally, there is known a scheme using an entropy encoding technology based on run-length/category encoding and variable-length encoding as part of the compression encoding technology for still images and moving images. This technology is also used for international standards such as the JPEG (Joint Photographic Expert Group) encoding scheme and the MPEG-1/-2 (Moving Picture Experts Group) encoding scheme.
In an event subjected to variable-length encoding in these encoding schemes, entropy encoding is performed by assigning a Huffman code to a two dimensional event called a runlength and level. That is, in JPEG or MPEG-1/-2, an encoded stream can be generated by only performing variable-length encoding for this one type of two dimensional event. Note that in the following description, an event subjected to variable-length encoding (information defined to be transmitted in a predetermined syntax, such as a DCT coefficient or motion vector) will be referred to as a syntax element hereinafter. In this case, a syntax is a rule for a compressed/encoded data string.
In entropy encoding based on the H. 264 encoding scheme which has recently attracted a great deal of attention as a high-efficiency encoding scheme, the runlengths and levels of transformation coefficients must be encoded as independent syntax elements. In addition, five syntax elements must be variable-length-encoded for each block. The five syntax elements include the total number (TotalCoeffs) of significant coefficients in a 4×4 block, the number (trailing_ones) of coefficients whose final significant coefficients are the absolute value “1” in a zigzag scan order, syntax element coeff_token of a two dimensional event, TotalZeros representing the number of transformation coefficients whose values are zero, and trailing_ones_sign representing the sign of a coefficient code with final significant coefficient being the absolute value “1” in the zigzag scan order. FIG. 1 shows a comparison between a variable-length encoding apparatus based on the JPEG or MPEG-1/-2 encoding scheme and one based on the H. 264 encoding scheme.
In entropy encoding for the H. 264 encoding scheme, transformation coefficients after an orthogonal transformation or image data are processed on a 4×4 block basis. In the H. 264 encoding scheme, the above five syntax elements are generated and variable-length-encoded by performing processing in a reverse order (reverse scan order) to the zigzag scan order in the 4×4 block shown in FIG. 2A. Note that the value of each transformation coefficient in the block is expressed as Level [I] with I representing a zigzag scan number.
<Entropy Encoding Processing in H. 264 Encoding Scheme>
Entropy encoding processing of a 4×4 block comprising transformation coefficients shown in FIG. 2B by a CAVLC scheme based on the H. 264 encoding scheme will be described next. FIG. 3 is a block diagram of a variable-length encoding apparatus based on the H. 264 encoding scheme. FIG. 4 shows the order in which variable-length codes corresponding to five syntax elements on a 4×4 block basis are combined to form an encoded stream.
A TotalCoeffs calculation unit 304 calculates the number of transformation coefficients in the 4×4 block in FIG. 2B which are not value 0. In this case, TotalCoeffs=6. A TotalZeros calculation unit 306 calculates the number of transformation coefficients whose Level [I] value is 0 between Level [9] and Level [0] as final significant coefficients. In this case, TotalZeros=4. A trailing_ones calculation unit 305 calculates the number of transformation coefficients, up to three, whose absolute values are 1 from Level [9] as final significant coefficients. In this case, since Level [9] and Level [7] correspond to the absolute value 1, trailing_ones=2. Note that a coeff_token variable-length code generation unit 309 calculates coeff_token as a syntax element in a two dimensional event from the value of TotalCoeffs calculated by the TotalCoeffs calculation unit 304 and the value of trailing_ones calculated by the trailing_ones calculation unit 305.
Since values of “Level” as a syntax element are sequentially generated in the reverse scan order, values of “Level” are sequentially generated from Level [9] as a final significant coefficient. However, the values of “Level” need to be corrected in accordance with the value of trailing_ones calculated by the trailing_ones calculation unit 305. A Level selection unit 301 performs this process. The Level selection unit 301 sequentially outputs transformation coefficients whose values of Level [I] are not 0 to a threshold determination unit 302 and a Level variable-length code generation unit 303. If the value of trailing_ones is smaller than 3, 1 is subtracted from the absolute value of first Level [I] whose absolute value is not 1. In this case, since trailing_ones=2, the value “5” obtained by subtracting 1 from the absolute value “6” of Level [6] is output. In addition, the threshold determination unit 302 determines suffixLength and outputs it to the Level variable-length code generation unit 303.
SuffixLength is determined by comparing a threshold table predetermined according to the H. 264 specifications with the input value of Level [I]. The Level variable-length code generation unit 303 selects a variable-length table (not shown) to be used for variable-length encoding in accordance with the value of SuffixLength.
A run_before calculation unit 307 sequentially calculates zero runs in the reverse scan order. For example, run_before=1 between Level [9] and Level [7], and run_before=0 between Level [7] and Level [6]. Note that a zeros_left managing unit outputs values obtained by subtracting sequentially calculated values of run_before from the values of TotalZeros, as zeros_left, to a run_before variable-length code generation unit 311. The run_before variable-length code generation unit 311 generates a variable-length code from the values of run_before and zeros_left.
A variable-length code combination unit 312 sequentially combines a variable-length code input from the coeff_token variable-length code generation unit 309, trailing_ones_sign input from the trailing_ones calculation unit 305, a variable-length code input from the Level variable-length code generation unit 303, a variable-length code input from a TotalZeros variable-length code generation unit 310, and a variable-length code input from the run_before variable-length code generation unit 311 in accordance with the order shown in FIG. 4, and outputs the resultant data as an encoded stream corresponding to FIG. 2B.
<Processing by Prior Art>
A case wherein entropy encoding is performed in hardware will be described with reference to the block diagram of FIG. 3. FIG. 5A and FIG. 5B show the relationship between each entropy encoding process and time in accordance with the prior art.
As transformation coefficients which are inputs in the block diagram of FIG. 3, 16 transformation coefficients in a 4×4 block in a process 503 shown in FIG. 5A are sequentially input to a process 506 and a process 510 in the reverse scan order. In the process 506, syntax elements TotalCoeffs and trailing_ones are calculated in parallel, and the coefficient sign trailing_ones_sign corresponding to trailing_ones is calculated. When the calculation of syntax elements TotalCoeffs and trailing_ones is complete, a variable-length code corresponding to coeff_token is generated from the values of these two syntax elements.
The generated one variable-length code and one sign trailing_ones_sign are generated into an encoded stream comprising coeff_token and trailing_ones_sign by a variable-length code combination unit 515 as indicated by the process 515. In the process 510, syntax element TotalZeros and a corresponding variable-length code are generated in parallel with the process 506. However, the generated one variable-length code is not combined as an encoded stream by the variable-length code combination unit in the process 515, and is held as an output from the process 510 at this point of time.
In a process 511, a variable-length code with Level [I] is generated. As indicated by the process 504, the same transformation coefficients as those input in the process 503 are input to the process 511 again. In the process 511, variable-length codes corresponding to values Level [I] of transformation coefficients input from a process 504 are output to the variable-length code combination unit for the process 515 as needed in accordance with the values of trailing_ones calculated in the process 506. The variable-length code combination unit in the process 515 combines a maximum of 16 variable-length codes, as needed, to generate an encoded stream comprising coeff_token, trailing_ones_sign, and Level.
When input operation from the process 511 is complete, the variable-length code combination unit in the process 515 combines TotalZeros held as an output from the process 510 to generate an encoded stream comprising coeff_token, trailing_ones_sign, Level, and TotalZeros.
In a process 514, a variable-length code of run_before is generated. As indicated by a process 505, the same transformation coefficients as those in the process 503 are sequentially input as in the process 504. In the process 514, variable-length codes of run_before are generated as needed from the values of syntax element TotalZeros which have already been calculated in the process 510 and values of Level [I] of the input transformation coefficients and are output to the variable-length code combination unit in the process 515. The variable-length code combination unit in the process 515 combines the variable-length codes of run_before with the encoded stream comprising coeff_token, trailing_ones_sign, Level, and TotalZeros as needed to complete the generation of the encoded stream of the 4×4 block.
The same processing is repeatedly performed for all 4×4 blocks in a picture, thereby realizing entropy encoding.
For example, an image encoding/decoding apparatus has been proposed, in which pipeline processing is realized by dividing the respective processes constituting encoding processing into stages, and providing memories before and after the processing stages, thereby achieving an increase in processing speed (see Japanese Patent Application Laid-open No. 11-252549).
In the prior art, however, in order to process one 4×4 block, the transformation coefficients of a 4×4 block need to be input three times (a total of three input operations to the processes 503, 504, and 505 described above). This requires an enormous processing time, leading to difficulties in realizing real-time encoding.
It is also difficult to apply the above proposed technique to entropy encoding like processing of a plurality of syntax elements as one encoded stream.